{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Time Taken to Cross the Door"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: timeTaken"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过门的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 个人，按从 <code>0</code> 到 <code>n - 1</code> 编号。现在有一扇门，每个人只能通过门进入或离开一次，耗时一秒。</p>\n",
    "\n",
    "<p>给你一个 <strong>非递减顺序</strong> 排列的整数数组 <code>arrival</code> ，数组长度为 <code>n</code> ，其中 <code>arrival[i]</code> 是第 <code>i</code> 个人到达门前的时间。另给你一个长度为 <code>n</code> 的数组 <code>state</code> ，其中 <code>state[i]</code> 是 <code>0</code> 则表示第 <code>i</code> 个人希望进入这扇门，是 <code>1</code> 则表示 TA 想要离开这扇门。</p>\n",
    "\n",
    "<p>如果 <strong>同时</strong> 有两个或更多人想要使用这扇门，则必须遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果前一秒 <strong>没有</strong> 使用门，那么想要 <strong>离开</strong> 的人会先离开。</li>\n",
    "\t<li>如果前一秒使用门 <strong>进入</strong> ，那么想要 <strong>进入</strong> 的人会先进入。</li>\n",
    "\t<li>如果前一秒使用门 <strong>离开</strong> ，那么想要 <strong>离开</strong> 的人会先离开。</li>\n",
    "\t<li>如果多个人都想朝同一方向走（都进入或都离开），编号最小的人会先通过门。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个长度为 <code>n</code> 的数组<em> </em><code>answer</code><em> </em>，其中<em> </em><code>answer[i]</code><em> </em>是第 <code>i</code> 个人通过门的时刻（秒）。</p>\n",
    "<strong>注意：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li>每秒只有一个人可以通过门。</li>\n",
    "\t<li>为遵循上述规则，一个人可以在到达门附近后等待，而不通过门进入或离开。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arrival = [0,1,1,2,4], state = [0,1,0,0,1]\n",
    "<strong>输出：</strong>[0,3,1,2,4]\n",
    "<strong>解释：</strong>每秒发生的情况如下：\n",
    "- t = 0 ：第 0 个人是唯一一个想要进入的人，所以 TA 可以直接进入。\n",
    "- t = 1 ：第 1 个人想要离开，第 2 个人想要进入。因为前一秒有人使用门进入，所以第 2 个人先进入。\n",
    "- t = 2 ：第 1 个人还是想要离开，第 3 个人想要进入。因为前一秒有人使用门进入，所以第 3 个人先进入。\n",
    "- t = 3 ：第 1 个人是唯一一个想要离开的人，所以 TA 可以直接离开。\n",
    "- t = 4 ：第 4 个人是唯一一个想要进入的人，所以 TA 可以直接离开。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arrival = [0,0,0], state = [1,0,1]\n",
    "<strong>输出：</strong>[0,2,1]\n",
    "<strong>解释：</strong>每秒发生的情况如下：\n",
    "- t = 0 ：第 1 个人想要进入，但是第 0 个人和第 2 个人都想要离开。因为前一秒没有使用门，所以想要离开的人会先离开。又因为第 0 个人的编号更小，所以 TA 先离开。\n",
    "- t = 1 ：第 1 个人想要进入，第 2 个人想要离开。因为前一秒有人使用门离开，所以第 2 个人先离开。\n",
    "- t = 2 ：第 1 个人是唯一一个想要进入的人，所以 TA 可以直接进入。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == arrival.length == state.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= arrival[i] &lt;= n</code></li>\n",
    "\t<li><code>arrival</code> 按 <strong>非递减顺序</strong> 排列</li>\n",
    "\t<li><code>state[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [time-taken-to-cross-the-door](https://leetcode.cn/problems/time-taken-to-cross-the-door/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [time-taken-to-cross-the-door](https://leetcode.cn/problems/time-taken-to-cross-the-door/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,1,2,4]\\n[0,1,0,0,1]', '[0,0,0]\\n[1,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        t,door=0,1#时间 门状态\n",
    "        #进门队员游标 出门队员游标\n",
    "        cur=[0,0]\n",
    "        while min(cur) < n:\n",
    "            #如果 两个游标最小的到达时间都大于 t \n",
    "            #把t移动到最小值 门重置到离开优先\n",
    "            if arrival[min(cur)]>t:\n",
    "                door=1\n",
    "                t=arrival[min(cur)]\n",
    "            while cur[door]<n and arrival[cur[door]]<=t:\n",
    "                    if state[cur[door]]==door:\n",
    "                        ans[cur[door]]=t\n",
    "                        t+=1\n",
    "                    cur[door]+=1\n",
    "            door^=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        leave, join = deque(), deque()\n",
    "        time, door, n = 0, 1, len(arrival)\n",
    "        answer = [0 for i in range(n)]\n",
    "        cur = [0,0]\n",
    "        while min(cur) < n:\n",
    "            if arrival[min(cur)] > time:\n",
    "                door = 1\n",
    "                time = arrival[min(cur)]\n",
    "            while cur[door] < n and arrival[cur[door]] <= time:\n",
    "                if state[cur[door]] == door:\n",
    "                    answer[cur[door]] = time\n",
    "                    time += 1\n",
    "                cur[door] += 1\n",
    "            door ^= 1\n",
    "        return answer\n",
    "        # for i in range(len(arrival)):\n",
    "        #     if state[i] == 0:\n",
    "        #         join.append((arrival[i], i))\n",
    "        #     else:\n",
    "        #         leave.append((arrival[i], i))\n",
    "        # for i in range(arrival[-1]+len(arrival)):\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        t,door=0,1#时间 门状态\n",
    "        #进门队员游标 出门队员游标\n",
    "        cur=[0,0]\n",
    "        while min(cur) < n:\n",
    "            #如果 两个游标最小的到达时间都大于 t \n",
    "            #把t移动到最小值 门重置到离开优先\n",
    "            if arrival[min(cur)]>t:\n",
    "                door=1\n",
    "                t=arrival[min(cur)]\n",
    "            while cur[door]<n and arrival[cur[door]]<=t:\n",
    "                    if state[cur[door]]==door:\n",
    "                        ans[cur[door]]=t\n",
    "                        t+=1\n",
    "                    cur[door]+=1\n",
    "            door^=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        t,door=0,1#时间 门状态\n",
    "        #进门队员游标 出门队员游标\n",
    "        et,lf=0,0\n",
    "        while et < n or lf < n:\n",
    "            #如果 两个游标最小的到达时间都大于 t \n",
    "            #把t移动到最小值 门重置到离开优先\n",
    "            if arrival[min(et,lf)]>t:\n",
    "                door=1\n",
    "                t=arrival[min(et,lf)]\n",
    "            #判断门状态\n",
    "            if door==1:\n",
    "                #还有离开的人 切离开的人时间小于 t \n",
    "                #移动游标直到不能离开\n",
    "                if lf<n and arrival[lf]<=t:\n",
    "                    while lf <n and arrival[lf]<=t:\n",
    "                        if state[lf]==1:\n",
    "                            ans[lf]=t\n",
    "                            t+=1\n",
    "                        lf+=1\n",
    "                #没有改变门状态\n",
    "                else:door=0\n",
    "                continue\n",
    "            if door==0:\n",
    "                #同上\n",
    "                if et<n and arrival[et]<=t:\n",
    "                    while et<n and arrival[et]<=t:\n",
    "                        if state[et]==0:\n",
    "                            ans[et]=t\n",
    "                            t+=1\n",
    "                        et+=1\n",
    "                else:door=1\n",
    "                continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]: # if no, 1 prefer\n",
    "        pre_one = -1\n",
    "        current_time = 0\n",
    "        current_index = 0\n",
    "        current_count = 0\n",
    "        n = len(arrival)\n",
    "        result = [-1] * len(arrival)\n",
    "        my_queue = [deque([]), deque([])]\n",
    "        while current_count < n:\n",
    "            while current_index < n and arrival[current_index] == current_time:\n",
    "                my_queue[state[current_index]].append(current_index)\n",
    "                current_index += 1\n",
    "            if not my_queue[0] and not my_queue[1]:\n",
    "                pre_one = -1\n",
    "            elif my_queue[0] and my_queue[1]:\n",
    "                if pre_one == -1:\n",
    "                    pre_one = 1\n",
    "                out_index = my_queue[pre_one].popleft()\n",
    "                result[out_index] = current_time\n",
    "                current_count += 1\n",
    "            elif my_queue[0]:\n",
    "                pre_one = 0\n",
    "                out_index = my_queue[0].popleft()\n",
    "                result[out_index] = current_time\n",
    "                current_count += 1\n",
    "            else:\n",
    "                pre_one = 1\n",
    "                out_index = my_queue[1].popleft()\n",
    "                result[out_index] = current_time\n",
    "                current_count += 1\n",
    "            current_time += 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        t,cur,door=0,0,1#时间 人员id游标 门状态\n",
    "        #2个队列 0 进门队列 1 出门队列\n",
    "        qq=[collections.deque(),collections.deque()]\n",
    "        #还有人 or 队列还有人\n",
    "        while cur<n or qq[0] or qq[1] :\n",
    "            #人员到达时间《=当前时间 释放出来\n",
    "            #自动释放到指定队列\n",
    "            while cur<n and arrival[cur]<=t:\n",
    "                qq[state[cur]].append(cur)\n",
    "                cur+=1\n",
    "            #如果队列都没人 这一秒就没人进 门变成1 离开优先\n",
    "            #同时 时间直接 变成下个人员到达时间\n",
    "            if not qq[0] and not qq[1]:\n",
    "                door=1\n",
    "                t=arrival[cur]\n",
    "                continue\n",
    "            #只有离开的人 没有进来的人 改变门状态\n",
    "            if qq[0] and not qq[1]:\n",
    "                door=0\n",
    "            #只有进来的 没有离开的人 改变门状态\n",
    "            elif qq[1] and not qq[0]:\n",
    "                door=1\n",
    "            #离开和进来的人都有 门状态保持不变\n",
    "            #一次性释放当前门状态队列的所有人\n",
    "            while qq[door]:\n",
    "                ans[qq[door].popleft()]=t\n",
    "                t+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        t,cur,door=0,0,1#时间 人员id游标 门状态\n",
    "        #2个队列 0 进门队列 1 出门队列\n",
    "        qq=[collections.deque(),collections.deque()]\n",
    "        #还有人 or 队列还有人\n",
    "        while cur<n or qq[0] or qq[1] :\n",
    "            #人员到达时间《=当前时间 释放出来\n",
    "            #自动释放到指定队列\n",
    "            while cur<n and arrival[cur]<=t:\n",
    "                qq[state[cur]].append(cur)\n",
    "                cur+=1\n",
    "            #如果队列都没人 这一秒就没人进 门变成1 离开优先\n",
    "            #同时 时间直接 变成下个人员到达时间\n",
    "            if not qq[0] and not qq[1]:\n",
    "                door=1\n",
    "                t=arrival[cur]\n",
    "                continue\n",
    "            #只有离开的人 没有进来的人 改变门状态\n",
    "            if qq[0] and not qq[1]:\n",
    "                door=0\n",
    "            #只有进来的 没有离开的人 改变门状态\n",
    "            elif qq[1] and not qq[0]:\n",
    "                door=1\n",
    "            #离开和进来的人都有 门状态保持不变\n",
    "            #一次性释放当前门状态队列的所有人\n",
    "            while qq[door]:\n",
    "                ans[qq[door].popleft()]=t\n",
    "                t+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "\n",
    "        res = [-1]*len(arrival)\n",
    "\n",
    "        p = 0 # 表示arrival里当前待进堆的位置\n",
    "        wait = [[],[]] # 2个优先队列放到一个列表里，就可以直接取用，不需要大量的if-else判断了\n",
    "        t = 0 # 表示当前时间\n",
    "        lt = -1 # 上一个通过门的人的通过时间\n",
    "        l = 1 #上一个通过门的人的类型，如果lt初值小于-1，l的初值设成什么都可以\n",
    "\n",
    "        while p<len(arrival) or wait[0] or wait[1]:\n",
    "            while p<len(arrival) and arrival[p]<=t: # 先把已经来到门前等待通过的人都放进优先队列\n",
    "                heapq.heappush(wait[state[p]],p)\n",
    "                p+=1\n",
    "            typ = l if t-lt==1 else 1 # 如果上一秒有人通过，那就和上一秒类型相同的优先，否则出门的优先\n",
    "            if wait[typ] or wait[typ^1]: # 注意这两个优先队列只要有一个不为空，这一秒就肯定有人要通过门\n",
    "                l = typ if wait[typ] else typ^1 # 如果优先的一边有人就让优先的一边先过，否则另一边过\n",
    "                res[heapq.heappop(wait[l])] = t\n",
    "                lt = t\n",
    "                t+=1\n",
    "            else:\n",
    "                t = arrival[p]  # 这说明没人等待，让时间快进到下一个等待的人能立即通过门，对这道题可以不用这么做而是把t+1放到if外面，但如果这么做，这个代码的时间复杂度将和arrival里的值无关        \n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        deque0,deque1=deque(),deque()\n",
    "        time,m=arrival[0],arrival[-1]\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        j=0\n",
    "        temp=2\n",
    "        while time<=m:\n",
    "            while j<n and time==arrival[j]:\n",
    "                if state[j]==0:\n",
    "                    deque0.append(j)\n",
    "                else :\n",
    "                    deque1.append(j)\n",
    "                j+=1\n",
    "            if (temp==0 and not deque0) or (temp==1 and not deque1):\n",
    "                temp=2\n",
    "            if temp==2 or temp==1:\n",
    "                if deque1:\n",
    "                    res=deque1.popleft()\n",
    "                    ans[res]=time\n",
    "                    temp=1\n",
    "                    time+=1\n",
    "                    continue\n",
    "            if temp==0 or temp==2:\n",
    "                if deque0:\n",
    "                    res=deque0.popleft()\n",
    "                    ans[res]=time\n",
    "                    temp=0\n",
    "                    time+=1\n",
    "                    continue\n",
    "            if (not deque0) and (not deque1):\n",
    "                temp=2\n",
    "            time+=1\n",
    "        if (temp==0 and not deque0) or (temp==1 and not deque1):\n",
    "            temp=2\n",
    "        if temp==2 or temp==1:\n",
    "            while deque1:\n",
    "                res=deque1.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "            while deque0:\n",
    "                res=deque0.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "        elif temp==2 or temp==0:\n",
    "            while deque0:\n",
    "                res=deque0.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "            while deque1:\n",
    "                res=deque1.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "\n",
    "        res = [-1]*len(arrival)\n",
    "\n",
    "        p = 0 # 表示arrival里当前待进堆的位置\n",
    "        wait = [[],[]] # 2个优先队列放到一个列表里，就可以直接取用，不需要大量的if-else判断了\n",
    "        t = 0 # 表示当前时间\n",
    "        lt = -1 # 上一个通过门的人的通过时间\n",
    "        l = 1 #上一个通过门的人的类型，如果lt初值小于-1，l的初值设成什么都可以\n",
    "\n",
    "        while p<len(arrival) or wait[0] or wait[1]:\n",
    "            while p<len(arrival) and arrival[p]<=t: # 先把已经来到门前等待通过的人都放进优先队列\n",
    "                heapq.heappush(wait[state[p]],p)\n",
    "                p+=1\n",
    "            typ = l if t-lt==1 else 1 # 如果上一秒有人通过，那就和上一秒类型相同的优先，否则出门的优先\n",
    "            if wait[typ] or wait[typ^1]: # 注意这两个优先队列只要有一个不为空，这一秒就肯定有人要通过门\n",
    "                l = typ if wait[typ] else typ^1 # 如果优先的一边有人就让优先的一边先过，否则另一边过\n",
    "                res[heapq.heappop(wait[l])] = t\n",
    "                lt = t\n",
    "                t+=1\n",
    "            else:\n",
    "                t = arrival[p]  # 这说明没人等待，让时间快进到下一个等待的人能立即通过门，对这道题可以不用这么做而是把t+1放到if外面，但如果这么做，这个代码的时间复杂度将和arrival里的值无关        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        res = [-1]*len(arrival)\n",
    "        p = 0 # 表示arrival里当前待进堆的位置\n",
    "        wait = [[],[]] # 2个优先队列放到一个列表里，就可以直接取用，不需要大量的if-else判断了\n",
    "        t = 0 # 表示当前时间\n",
    "        lt = -1 # 上一个通过门的人的通过时间\n",
    "        l = 1 #上一个通过门的人的类型，如果lt初值小于-1，l的初值设成什么都可以\n",
    "\n",
    "        while p<len(arrival) or wait[0] or wait[1]:\n",
    "            while p<len(arrival) and arrival[p]<=t: # 先把已经来到门前等待通过的人都放进优先队列\n",
    "                heapq.heappush(wait[state[p]],p)\n",
    "                p+=1\n",
    "            typ = l if t-lt==1 else 1 # 如果上一秒有人通过，那就和上一秒类型相同的优先，否则出门的优先\n",
    "            if wait[typ] or wait[typ^1]: # 注意这两个优先队列只要有一个不为空，这一秒就肯定有人要通过门\n",
    "                l = typ if wait[typ] else typ^1 # 如果优先的一边有人就让优先的一边先过，否则另一边过\n",
    "                res[heapq.heappop(wait[l])] = t\n",
    "                lt = t\n",
    "                t+=1\n",
    "            else:\n",
    "                t = arrival[p]  # 这说明没人等待，让时间快进到下一个等待的人能立即通过门，对这道题可以不用这么做而是把t+1放到if外面，但如果这么做，这个代码的时间复杂度将和arrival里的值无关        \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\r\n",
    "\r\n",
    "        res = [-1]*len(arrival)\r\n",
    "\r\n",
    "        p = 0 # 表示arrival里当前待进堆的位置\r\n",
    "        wait = [[],[]] # 2个优先队列放到一个列表里，就可以直接取用，不需要大量的if-else判断了\r\n",
    "        t = 0 # 表示当前时间\r\n",
    "        lt = -1 # 上一个通过门的人的通过时间\r\n",
    "        l = 1 #上一个通过门的人的类型，如果lt初值小于-1，l的初值设成什么都可以\r\n",
    "\r\n",
    "        while p<len(arrival) or wait[0] or wait[1]:\r\n",
    "            while p<len(arrival) and arrival[p]<=t: # 先把已经来到门前等待通过的人都放进优先队列\r\n",
    "                heapq.heappush(wait[state[p]],p)\r\n",
    "                p+=1\r\n",
    "            typ = l if t-lt==1 else 1 # 如果上一秒有人通过，那就和上一秒类型相同的优先，否则出门的优先\r\n",
    "            if wait[typ] or wait[typ^1]: # 注意这两个优先队列只要有一个不为空，这一秒就肯定有人要通过门\r\n",
    "                l = typ if wait[typ] else typ^1 # 如果优先的一边有人就让优先的一边先过，否则另一边过\r\n",
    "                res[heapq.heappop(wait[l])] = t\r\n",
    "                lt = t\r\n",
    "                t+=1\r\n",
    "            else:\r\n",
    "                t = arrival[p]  # 这说明没人等待，让时间快进到下一个等待的人能立即通过门，对这道题可以不用这么做而是把t+1放到if外面，但如果这么做，这个代码的时间复杂度将和arrival里的值无关        \r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        qq = [collections.deque(), collections.deque()]\n",
    "        t, cur, door = 0, 0, 1\n",
    "        n = len(arrival)\n",
    "        ans = [0]*n\n",
    "        while cur < n or qq[0] or qq[1]:\n",
    "            while cur < n and arrival[cur] <=t:\n",
    "                qq[state[cur]].append(cur)\n",
    "                cur += 1\n",
    "            if not qq[0] and not qq[1]:\n",
    "                door = 1\n",
    "                t = arrival[cur]\n",
    "                continue\n",
    "            if qq[0] and not qq[1]:\n",
    "                door = 0\n",
    "            elif not qq[0] and qq[1]:\n",
    "                door = 1\n",
    "            while qq[door]:\n",
    "                ans[qq[door].popleft()] = t\n",
    "                t += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        from collections import deque\n",
    "        enterQueue, exitQueue = deque([]), deque([])\n",
    "        arrivalIndex = 0\n",
    "        curTime = 0\n",
    "        ans = [-1]*len(arrival)\n",
    "        prev = 0 # 0 if previous second not used or used for exiting, 1 if previous second used for entering\n",
    "        while arrivalIndex < len(arrival) or enterQueue or exitQueue:\n",
    "            # print(arrivalIndex, enterQueue, exitQueue)\n",
    "            while arrivalIndex < len(arrival) and arrival[arrivalIndex] <= curTime:\n",
    "                if state[arrivalIndex] == 0:\n",
    "                    enterQueue.append(arrivalIndex)\n",
    "                else:\n",
    "                    exitQueue.append(arrivalIndex)\n",
    "                arrivalIndex += 1\n",
    "            if prev:\n",
    "                if enterQueue:\n",
    "                    new_enter = enterQueue.popleft()\n",
    "                    ans[new_enter] = curTime\n",
    "                elif exitQueue:\n",
    "                    new_exit = exitQueue.popleft()\n",
    "                    ans[new_exit] = curTime\n",
    "                    prev = 0\n",
    "                else:\n",
    "                    prev = 0\n",
    "            else:\n",
    "                if exitQueue:\n",
    "                    new_exit = exitQueue.popleft()\n",
    "                    ans[new_exit] = curTime\n",
    "                elif enterQueue:\n",
    "                    new_enter = enterQueue.popleft()\n",
    "                    ans[new_enter] = curTime\n",
    "                    prev = 1\n",
    "            curTime += 1\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        # 模拟队列\n",
    "        n=len(arrival)\n",
    "        door_status=-1 # -1表示未使用，0表示进入，1表示离开\n",
    "        in_queue=deque()\n",
    "        out_queue=deque()\n",
    "        idx=0\n",
    "        time=0\n",
    "        ans=[0]*n\n",
    "        while idx<n or in_queue or out_queue:\n",
    "            # 首先，将time时刻的所有人放入队列中\n",
    "            while idx<n and arrival[idx]==time:\n",
    "                if state[idx]:\n",
    "                    out_queue.append(idx)\n",
    "                else:\n",
    "                    in_queue.append(idx)\n",
    "                idx+=1\n",
    "            # 然后，根据前一时刻门的状态确定通过顺序\n",
    "            if len(in_queue)==0 and len(out_queue)==0:\n",
    "                # 当前时刻门未使用\n",
    "                door_status=-1\n",
    "            else:\n",
    "                if door_status!=0:\n",
    "                    # 此时优先离开\n",
    "                    if len(out_queue)>0:\n",
    "                        person=out_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=1\n",
    "                    else:\n",
    "                        person=in_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=0\n",
    "                else:\n",
    "                    # 此时优先进入\n",
    "                    if len(in_queue)>0:\n",
    "                        person=in_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=0\n",
    "                    else:\n",
    "                        person=out_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=1\n",
    "            time+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        qs = [deque(), deque()]\n",
    "        m = len(arrival)\n",
    "        t = 0\n",
    "        i = 0\n",
    "        ans = [0] * m\n",
    "        door = 1\n",
    "\n",
    "        while i < m or qs[0] or qs[1]:\n",
    "            while i < m and arrival[i] <= t:\n",
    "                qs[state[i]].append(i)\n",
    "                i += 1\n",
    "            \n",
    "            if not qs[0] and not qs[1]:\n",
    "                t = arrival[i]\n",
    "                door = 1\n",
    "                continue\n",
    "            if not qs[0]:\n",
    "                door = 1\n",
    "            elif not qs[1]:\n",
    "                door = 0\n",
    "            \n",
    "            while qs[door]:\n",
    "                ans[qs[door].popleft()] = t\n",
    "                t += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        # 模拟队列\n",
    "        n=len(arrival)\n",
    "        door_status=-1 # -1表示未使用，0表示进入，1表示离开\n",
    "        in_queue=deque()\n",
    "        out_queue=deque()\n",
    "        idx=0\n",
    "        time=0\n",
    "        ans=[0]*n\n",
    "        while idx<n or in_queue or out_queue:\n",
    "            # 首先，将time时刻的所有人放入队列中\n",
    "            while idx<n and arrival[idx]==time:\n",
    "                if state[idx]:\n",
    "                    out_queue.append(idx)\n",
    "                else:\n",
    "                    in_queue.append(idx)\n",
    "                idx+=1\n",
    "            # 然后，根据前一时刻门的状态确定通过顺序\n",
    "            if len(in_queue)==0 and len(out_queue)==0:\n",
    "                # 当前时刻门未使用\n",
    "                door_status=-1\n",
    "            else:\n",
    "                if door_status!=0:\n",
    "                    # 此时优先离开\n",
    "                    if len(out_queue)>0:\n",
    "                        person=out_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=1\n",
    "                    else:\n",
    "                        person=in_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=0\n",
    "                else:\n",
    "                    # 此时优先进入\n",
    "                    if len(in_queue)>0:\n",
    "                        person=in_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=0\n",
    "                    else:\n",
    "                        person=out_queue.popleft()\n",
    "                        ans[person]=time\n",
    "                        door_status=1\n",
    "            time+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        deque0,deque1=deque(),deque()\n",
    "        time,m=arrival[0],arrival[-1]\n",
    "        n=len(arrival)\n",
    "        ans=[0]*n\n",
    "        j=0\n",
    "        temp=2\n",
    "        while time<=m:\n",
    "            while j<n and time==arrival[j]:\n",
    "                if state[j]==0:\n",
    "                    deque0.append(j)\n",
    "                else :\n",
    "                    deque1.append(j)\n",
    "                j+=1\n",
    "            if (temp==0 and not deque0) or (temp==1 and not deque1):\n",
    "                temp=2\n",
    "            if temp==2 or temp==1:\n",
    "                if deque1:\n",
    "                    res=deque1.popleft()\n",
    "                    ans[res]=time\n",
    "                    temp=1\n",
    "                    time+=1\n",
    "                    continue\n",
    "            if temp==0 or temp==2:\n",
    "                if deque0:\n",
    "                    res=deque0.popleft()\n",
    "                    ans[res]=time\n",
    "                    temp=0\n",
    "                    time+=1\n",
    "                    continue\n",
    "            if (not deque0) and (not deque1):\n",
    "                temp=2\n",
    "                time=arrival[j]\n",
    "                continue\n",
    "            time+=1\n",
    "        if (temp==0 and not deque0) or (temp==1 and not deque1):\n",
    "            temp=2\n",
    "        if temp==2 or temp==1:\n",
    "            while deque1:\n",
    "                res=deque1.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "            while deque0:\n",
    "                res=deque0.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "        elif temp==2 or temp==0:\n",
    "            while deque0:\n",
    "                res=deque0.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "            while deque1:\n",
    "                res=deque1.popleft()\n",
    "                ans[res]=time\n",
    "                time+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        enter_q = []\n",
    "        exit_q = []\n",
    "        pre = None\n",
    "        i = 0\n",
    "        curr = 0\n",
    "        used = False\n",
    "        result = [0 for _ in range(len(arrival))]\n",
    "        person = None\n",
    "        while i < len(arrival) or enter_q or exit_q:\n",
    "            while i < len(arrival) and arrival[i] == curr:\n",
    "                if state[i] == 0:\n",
    "                    heapq.heappush(enter_q, i)\n",
    "                else:\n",
    "                    heapq.heappush(exit_q, i)\n",
    "                i+=1\n",
    "            if exit_q:\n",
    "                if enter_q:\n",
    "                    if pre == 0:\n",
    "                        person = (heapq.heappop(enter_q))\n",
    "                    else:\n",
    "                        person = heapq.heappop(exit_q)\n",
    "                else:\n",
    "                    person = heapq.heappop(exit_q)\n",
    "                    pre = 1\n",
    "            elif enter_q:\n",
    "                person = heapq.heappop(enter_q)\n",
    "                pre = 0\n",
    "            else:\n",
    "                pre = None\n",
    "                person = None\n",
    "            if person is not None:\n",
    "                result[person] = curr\n",
    "            curr += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def timeTaken(self, time, direction):\n",
    "        wait_direction_in = []\n",
    "        wait_direction_out = []\n",
    "        last_direction = None\n",
    "        now_time = 0\n",
    "        person_idx = 0\n",
    "        num_of_person = len(time)\n",
    "\n",
    "        return_res = [0] * num_of_person\n",
    "        while person_idx < num_of_person or wait_direction_in or wait_direction_out:\n",
    "            while person_idx < num_of_person and time[person_idx] == now_time:\n",
    "                if direction[person_idx] == 0:\n",
    "                    heapq.heappush(wait_direction_in, person_idx)\n",
    "                else:\n",
    "                    heapq.heappush(wait_direction_out, person_idx)\n",
    "                person_idx += 1\n",
    "\n",
    "            if wait_direction_in:\n",
    "                if wait_direction_out:\n",
    "                    if last_direction == 0:\n",
    "                        index = heapq.heappop(wait_direction_in)\n",
    "                    else:\n",
    "                        index = heapq.heappop(wait_direction_out)\n",
    "                else:\n",
    "                    index = heapq.heappop(wait_direction_in)\n",
    "                    last_direction = 0\n",
    "            elif wait_direction_out:\n",
    "                index = heapq.heappop(wait_direction_out)\n",
    "                last_direction = 1\n",
    "            else:\n",
    "                index = None\n",
    "                last_direction = None\n",
    "\n",
    "            if index is not None:\n",
    "                print(index)\n",
    "                return_res[index] = now_time\n",
    "            now_time += 1\n",
    "\n",
    "        return return_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        res = [-1] * len(arrival)\n",
    "        p = 0;\n",
    "        import heapq\n",
    "        wait = [[] for _ in range(2)]  # Create a list of two empty priority queues\n",
    "        t = 0;\n",
    "        lt = -1;\n",
    "        l = 1;\n",
    "        \n",
    "        while p < len(arrival) or len(wait[0]) != 0 or len(wait[1]) != 0:\n",
    "            while p<len(arrival) and arrival[p] <= t:\n",
    "                heapq.heappush(wait[state[p]], p);\n",
    "                p+=1;\n",
    "            typ = 1;\n",
    "            if t-lt == 1:\n",
    "                typ = l;\n",
    "            if len(wait[0])!=0 or len(wait[1])!=0:\n",
    "                if len(wait[typ])!=0:\n",
    "                    l = typ;\n",
    "                else:\n",
    "                    l = typ ^ 1;\n",
    "                res[heapq.heappop(wait[l])] = t;\n",
    "                lt = t;\n",
    "                t+=1;\n",
    "            else:\n",
    "                 t =arrival[p];\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def timeTaken(self, time, direction):\n",
    "        wait_direction_in = []\n",
    "        wait_direction_out = []\n",
    "        last_direction = None\n",
    "        now_time = 0\n",
    "        person_idx = 0\n",
    "        num_of_person = len(time)\n",
    "\n",
    "        return_res = [0] * num_of_person\n",
    "        while person_idx < num_of_person or wait_direction_in or wait_direction_out:\n",
    "            while person_idx < num_of_person and time[person_idx] == now_time:\n",
    "                if direction[person_idx] == 0:\n",
    "                    heapq.heappush(wait_direction_in, person_idx)\n",
    "                else:\n",
    "                    heapq.heappush(wait_direction_out, person_idx)\n",
    "                person_idx += 1\n",
    "\n",
    "            if wait_direction_in:\n",
    "                if wait_direction_out:\n",
    "                    if last_direction == 0:\n",
    "                        index = heapq.heappop(wait_direction_in)\n",
    "                    else:\n",
    "                        index = heapq.heappop(wait_direction_out)\n",
    "                else:\n",
    "                    index = heapq.heappop(wait_direction_in)\n",
    "                    last_direction = 0\n",
    "            elif wait_direction_out:\n",
    "                index = heapq.heappop(wait_direction_out)\n",
    "                last_direction = 1\n",
    "            else:\n",
    "                index = None\n",
    "                last_direction = None\n",
    "\n",
    "            if index is not None:\n",
    "                print(index)\n",
    "                return_res[index] = now_time\n",
    "            now_time += 1\n",
    "\n",
    "        return return_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def timeTaken(self, time, direction):\n",
    "        wait_direction_in = []\n",
    "        wait_direction_out = []\n",
    "        last_direction = None\n",
    "        now_time = 0\n",
    "        person_idx = 0\n",
    "        num_of_person = len(time)\n",
    "\n",
    "        return_res = [0] * num_of_person\n",
    "        while person_idx < num_of_person or wait_direction_in or wait_direction_out:\n",
    "            while person_idx < num_of_person and time[person_idx] == now_time:\n",
    "                if direction[person_idx] == 0:\n",
    "                    heapq.heappush(wait_direction_in, person_idx)\n",
    "                else:\n",
    "                    heapq.heappush(wait_direction_out, person_idx)\n",
    "                person_idx += 1\n",
    "\n",
    "            if wait_direction_in:\n",
    "                if wait_direction_out:\n",
    "                    if last_direction == 0:\n",
    "                        index = heapq.heappop(wait_direction_in)\n",
    "                    else:\n",
    "                        index = heapq.heappop(wait_direction_out)\n",
    "                else:\n",
    "                    index = heapq.heappop(wait_direction_in)\n",
    "                    last_direction = 0\n",
    "            elif wait_direction_out:\n",
    "                index = heapq.heappop(wait_direction_out)\n",
    "                last_direction = 1\n",
    "            else:\n",
    "                index = None\n",
    "                last_direction = None\n",
    "\n",
    "            if index is not None:\n",
    "                print(index)\n",
    "                return_res[index] = now_time\n",
    "            now_time += 1\n",
    "\n",
    "        return return_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def timeTaken(self, time, direction):\n",
    "        wait_direction_in = []\n",
    "        wait_direction_out = []\n",
    "        last_direction = None\n",
    "        now_time = 0\n",
    "        person_idx = 0\n",
    "        num_of_person = len(time)\n",
    "\n",
    "        return_res = [0] * num_of_person\n",
    "        while person_idx < num_of_person or wait_direction_in or wait_direction_out:\n",
    "            while person_idx < num_of_person and time[person_idx] == now_time:\n",
    "                if direction[person_idx] == 0:\n",
    "                    heapq.heappush(wait_direction_in, person_idx)\n",
    "                else:\n",
    "                    heapq.heappush(wait_direction_out, person_idx)\n",
    "                person_idx += 1\n",
    "\n",
    "            if wait_direction_in:\n",
    "                if wait_direction_out:\n",
    "                    if last_direction == 0:\n",
    "                        index = heapq.heappop(wait_direction_in)\n",
    "                    else:\n",
    "                        index = heapq.heappop(wait_direction_out)\n",
    "                else:\n",
    "                    index = heapq.heappop(wait_direction_in)\n",
    "                    last_direction = 0\n",
    "            elif wait_direction_out:\n",
    "                index = heapq.heappop(wait_direction_out)\n",
    "                last_direction = 1\n",
    "            else:\n",
    "                index = None\n",
    "                last_direction = None\n",
    "\n",
    "            if index is not None:\n",
    "                print(index)\n",
    "                return_res[index] = now_time\n",
    "            now_time += 1\n",
    "\n",
    "        return return_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        enter_q = []\n",
    "        exit_q = []\n",
    "        pre = None\n",
    "        i = 0\n",
    "        curr = 0\n",
    "        result = [0 for _ in range(len(arrival))]\n",
    "        person = None\n",
    "        while i < len(arrival) or enter_q or exit_q:\n",
    "            while i < len(arrival) and arrival[i] == curr:\n",
    "                if state[i] == 0:\n",
    "                    heapq.heappush(enter_q, i)\n",
    "                else:\n",
    "                    heapq.heappush(exit_q, i)\n",
    "                i+=1\n",
    "            if exit_q:\n",
    "                if enter_q:\n",
    "                    if pre == 0:\n",
    "                        person = (heapq.heappop(enter_q))\n",
    "                    else:\n",
    "                        person = heapq.heappop(exit_q)\n",
    "                else:\n",
    "                    person = heapq.heappop(exit_q)\n",
    "                    pre = 1\n",
    "            elif enter_q:\n",
    "                person = heapq.heappop(enter_q)\n",
    "                pre = 0\n",
    "            else:\n",
    "                pre = None\n",
    "                person = None\n",
    "            if person is not None:\n",
    "                result[person] = curr\n",
    "            curr += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        inPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 0]\n",
    "        outPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 1]\n",
    "\n",
    "        inPerson.reverse()\n",
    "        outPerson.reverse()\n",
    "\n",
    "        t = 0\n",
    "        lastType = 0\n",
    "        lattTime = -2\n",
    "        ans = [0] * len(arrival)\n",
    "        while inPerson or outPerson:\n",
    "            a = inPerson and inPerson[-1][1] <= t\n",
    "            b = outPerson and outPerson[-1][1] <= t\n",
    "            \n",
    "            if not a and not b:\n",
    "                atime = inPerson[-1][1] if inPerson else float('inf')\n",
    "                btime = outPerson[-1][1] if outPerson else float('inf')\n",
    "                t += min(atime - t, btime - t)\n",
    "                lastType = 0\n",
    "                lattTime = -2\n",
    "            elif a and b:\n",
    "                if lastType == 0 and t == lattTime:\n",
    "                    curIndex, _ = inPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 0\n",
    "                else:\n",
    "                    curIndex, _ = outPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 1\n",
    "            else:\n",
    "                type = 0 if inPerson and inPerson[-1][1] <= t else 1\n",
    "                curIndex, _ = (inPerson.pop()) if inPerson and inPerson[-1][1] <= t else (outPerson.pop())\n",
    "                ans[curIndex] = t\n",
    "                t += 1\n",
    "                lattTime = t\n",
    "                lastType = type\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        inPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 0]\n",
    "        outPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 1]\n",
    "\n",
    "        inPerson.reverse()\n",
    "        outPerson.reverse()\n",
    "\n",
    "        t = 0\n",
    "        lastType = 0\n",
    "        lattTime = -2\n",
    "        ans = [0] * len(arrival)\n",
    "        while inPerson or outPerson:\n",
    "            \n",
    "            a = b = 0\n",
    "            if inPerson and inPerson[-1][1] <= t:\n",
    "                a = 1\n",
    "            if outPerson and outPerson[-1][1] <= t:\n",
    "                b = 1\n",
    "                \n",
    "    \n",
    "            if not a and not b:\n",
    "                atime = inPerson[-1][1] if inPerson else float('inf')\n",
    "                btime = outPerson[-1][1] if outPerson else float('inf')\n",
    "                t += min(atime - t, btime - t)\n",
    "                lastType = 0\n",
    "                lattTime = -2\n",
    "            elif a and b:\n",
    "                if lastType == 0 and t == lattTime:\n",
    "                    curIndex, _ = inPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 0\n",
    "                else:\n",
    "                    curIndex, _ = outPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 1\n",
    "            else:\n",
    "                type = 0 if inPerson and inPerson[-1][1] <= t else 1\n",
    "                curIndex, _ = (inPerson.pop()) if inPerson and inPerson[-1][1] <= t else (outPerson.pop())\n",
    "                ans[curIndex] = t\n",
    "                t += 1\n",
    "                lattTime = t\n",
    "                lastType = type\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        inPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 0]\n",
    "        outPerson = [(index, arrival[index]) for index, t in enumerate(state) if t == 1]\n",
    "\n",
    "        inPerson.reverse()\n",
    "        outPerson.reverse()\n",
    "\n",
    "        t = 0\n",
    "        lastType = 0\n",
    "        lattTime = -2\n",
    "        ans = [0] * len(arrival)\n",
    "        while inPerson or outPerson:\n",
    "            \n",
    "            a = b = 0\n",
    "            if inPerson and inPerson[-1][1] <= t:\n",
    "                a = 1\n",
    "            if outPerson and outPerson[-1][1] <= t:\n",
    "                b = 1\n",
    "                \n",
    "    \n",
    "            if not a and not b:\n",
    "                # atime = inPerson[-1][1] if inPerson else float('inf')\n",
    "                # btime = outPerson[-1][1] if outPerson else float('inf')\n",
    "                # t += min(atime - t, btime - t)\n",
    "                t += 1\n",
    "                lastType = 0\n",
    "                lattTime = -2\n",
    "            elif a and b:\n",
    "                if lastType == 0 and t == lattTime:\n",
    "                    curIndex, _ = inPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 0\n",
    "                else:\n",
    "                    curIndex, _ = outPerson.pop()\n",
    "                    ans[curIndex] = t\n",
    "                    t += 1\n",
    "                    lattTime = t\n",
    "                    lastType = 1\n",
    "            else:\n",
    "                type = 0 if inPerson and inPerson[-1][1] <= t else 1\n",
    "                curIndex, _ = (inPerson.pop()) if inPerson and inPerson[-1][1] <= t else (outPerson.pop())\n",
    "                ans[curIndex] = t\n",
    "                t += 1\n",
    "                lattTime = t\n",
    "                lastType = type\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        n = len(arrival)\n",
    "        people = [(time, kind, id) for id, (time, kind) in enumerate(zip(arrival, state))]\n",
    "        people.sort(key=lambda x: x[0])\n",
    "\n",
    "        pq = [[], []]  # pq[0] for enter, pq[1] for exit\n",
    "        remain, curTime = n, 0\n",
    "        ei = 0\n",
    "        preState = 1  # 0: enter, 1: exit\n",
    "        res = [0] * n\n",
    "        while remain > 0:\n",
    "            while ei < n and people[ei][0] <= curTime:\n",
    "                _, kind, id = people[ei]\n",
    "                heappush(pq[kind], id)\n",
    "                ei += 1\n",
    "            if pq[0] or pq[1]:\n",
    "                kind = preState if pq[preState] else preState ^ 1\n",
    "                id = heappop(pq[kind])\n",
    "                res[id] = curTime\n",
    "                remain -= 1\n",
    "                curTime += 1\n",
    "                preState = kind\n",
    "            elif ei < n:\n",
    "                curTime = people[ei][0]\n",
    "                preState = 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from heapq import heapify, heappop, heappush, heappushpop\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param arrival:\n",
    "        :param state:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        for k, v in enumerate(zip(arrival, state)):\n",
    "            ll.append((v[0], v[1], k))\n",
    "        ll.sort(key=lambda x: (x[0], -x[1]))\n",
    "        st = None\n",
    "        leaveQ = []\n",
    "        heapify(leaveQ)\n",
    "        enterQ = []\n",
    "        heapify(enterQ)\n",
    "        ret = []\n",
    "        ll = deque(ll)\n",
    "        for i in range(0, 10**9+7):\n",
    "            if len(leaveQ) == 0 and len(enterQ) == 0 and len(ll) == 0:\n",
    "                break\n",
    "            while ll and ll[0][0] <= i:\n",
    "                cur = ll.popleft()\n",
    "                if cur[1] == 1:\n",
    "                    heappush(leaveQ, (cur[2], cur[0]))\n",
    "                else:\n",
    "                    heappush(enterQ, (cur[2], cur[0]))\n",
    "            oper = False\n",
    "            if st is None or st == 1:\n",
    "                if leaveQ:\n",
    "                    res = heappop(leaveQ)\n",
    "                    ret.append((i, res[0]))\n",
    "                    st = 1\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if enterQ:\n",
    "                        res = heappop(enterQ)\n",
    "                        ret.append((i, res[0]))\n",
    "                        st = 0\n",
    "                        oper = True\n",
    "            else:\n",
    "                if enterQ:\n",
    "                    res = heappop(enterQ)\n",
    "                    ret.append((i, res[0]))\n",
    "                    st = 0\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if leaveQ:\n",
    "                        res = heappop(leaveQ)\n",
    "                        ret.append((i, res[0]))\n",
    "                        st = 1\n",
    "                        oper = True\n",
    "\n",
    "            if oper is False:\n",
    "                st = None\n",
    "\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from heapq import heapify, heappop, heappush, heappushpop\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param arrival:\n",
    "        :param state:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        for k, v in enumerate(zip(arrival, state)):\n",
    "            ll.append((v[0], v[1], k))\n",
    "        ll.sort(key=lambda x: (x[0], -x[1]))\n",
    "        st = None\n",
    "        leaveQ = []\n",
    "        heapify(leaveQ)\n",
    "        enterQ = []\n",
    "        heapify(enterQ)\n",
    "        ret = []\n",
    "        ll = deque(ll)\n",
    "\n",
    "        for i in range(0, (max(arrival) +1) *10 ):\n",
    "            if len(leaveQ) == 0 and len(enterQ) == 0 and len(ll) == 0:\n",
    "                break\n",
    "\n",
    "            while ll and ll[0][0] <= i:\n",
    "                cur = ll.popleft()\n",
    "                if cur[1] == 1:\n",
    "                    heappush(leaveQ, (cur[2], cur[0]))\n",
    "\n",
    "                else:\n",
    "                    heappush(enterQ, (cur[2], cur[0]))\n",
    "\n",
    "            oper = False\n",
    "            if st is None or st == 1:\n",
    "                if leaveQ:\n",
    "                    res = heappop(leaveQ)\n",
    "                    ret.append((i, res[0]))\n",
    "                    st = 1\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if enterQ:\n",
    "                        res = heappop(enterQ)\n",
    "                        ret.append((i, res[0]))\n",
    "                        st = 0\n",
    "                        oper = True\n",
    "            else:\n",
    "                if enterQ:\n",
    "                    res = heappop(enterQ)\n",
    "                    ret.append((i, res[0]))\n",
    "                    st = 0\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if leaveQ:\n",
    "                        res = heappop(leaveQ)\n",
    "                        ret.append((i, res[0]))\n",
    "                        st = 1\n",
    "                        oper = True\n",
    "\n",
    "            if oper is False:\n",
    "                st = None\n",
    "\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "\n",
    "        return [i[0] for i in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param arrival:\n",
    "        :param state:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = []\n",
    "        for k, v in enumerate(zip(arrival, state)):\n",
    "            ll.append((v[0], v[1], k))\n",
    "        ll.sort(key=lambda x: (x[0], -x[1]))\n",
    "        ll = deque(ll)\n",
    "        st = None\n",
    "        leaveQ = SortedList(key=lambda x: x[1])\n",
    "        enterQ = SortedList(key=lambda x: x[1])\n",
    "        ret = []\n",
    "        for i in range(0, (max(arrival) +1) * 100):\n",
    "            if len(leaveQ) == 0 and len(enterQ) == 0 and len(ll) == 0:\n",
    "                break\n",
    "\n",
    "            while ll and ll[0][0] <= i:\n",
    "                cur = ll.popleft()\n",
    "                if cur[1] == 1:\n",
    "                    leaveQ.add((cur[0], cur[2]))\n",
    "                else:\n",
    "                    enterQ.add((cur[0], cur[2]))\n",
    "            oper = False\n",
    "            if st is None or st == 1:\n",
    "                if leaveQ:\n",
    "                    res = leaveQ.pop(0)\n",
    "                    ret.append((i, res[1]))\n",
    "                    st = 1\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if enterQ:\n",
    "                        res = enterQ.pop(0)\n",
    "                        ret.append((i, res[1]))\n",
    "                        st = 0\n",
    "                        oper = True\n",
    "            else:\n",
    "                if enterQ:\n",
    "                    res = enterQ.pop(0)\n",
    "                    ret.append((i, res[1]))\n",
    "                    st = 0\n",
    "                    oper = True\n",
    "                else:\n",
    "                    if leaveQ:\n",
    "                        res = leaveQ.pop(0)\n",
    "                        ret.append((i, res[1]))\n",
    "                        st = 1\n",
    "                        oper = True\n",
    "\n",
    "            if oper is False:\n",
    "                st = None\n",
    "\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "\n",
    "        return [i[0] for i in ret]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
